The present invention relates generally to behavioral synthesis, and more particularly to behavioral synthesis linked to logic synthesis.
The following co-pending U.S. patent application, which is herein incorporated by reference, represents background to the present invention: xe2x80x9cBehavioral Synthesis Links To Logic Synthesis,xe2x80x9d filed on May 12, 1995, with inventors Ronald A. Miller, Donald B. MacMillen, Tai A. Ly and David W. Knapp, having McDermott, Will and Emery docket number of 49725-021 and U.S. Pat. Ser. No. 08/440,101. This co-pending application will hereinafter be referred to as the Miller application.
Behavioral synthesis allows the designer of complex digital integrated circuits to specify the design at a relatively high-level of abstraction, which provides a variety of advantages in the design process. In particular, behavioral synthesis allows the design to be specified in a high-level hardware description language (HLHDL) that is more oriented towards expressing the desired behavior than the underlying hardware mechanisms by which such behavior will be accomplished. Some of the advantages of such behavioral HLHDL specifications are as follows. Since behavioral descriptions are closer to the overall behavior desired, they tend to be more intuitive and easier for the circuit designer to write. Behavioral descriptions tend to be shorter than more hardware-oriented descriptions and therefore tend to be quicker to write. Because behavioral descriptions are at a high-level of abstraction, they tend to simulate much faster than lower-level descriptions. All of these above advantages enhance the ability of the circuit designer to explore architectural alternatives and a variety of design trade-offs.
The basic process by which behavioral synthesis is accomplished, according to the Miller application, is shown in FIG. 1. The process of FIG. 1 is accomplished by the xe2x80x9cBehavioral Compilerxe2x80x9d product of Synopsys, Inc., 700 East Middlefield Road, Mountain View, Calif. The input representation is an HLHDL such as IEEE Standard 1076-1993 VHDL or IEEE Standard 1364-1995 Verilog HDL, both of which are herein incorporated by reference. Step 1510 translates the HLHDL into a xe2x80x9cregister transfer levelxe2x80x9d (RTL) description that includes high-level (i.e., multi-bit): functional units (with no delay or area information) and multiplexors. In contrast to the translation process as applied to conventional RTL synthesis, the current translation process does not infer any sequential elements. As a result, this netlist representation produced by the translation process only models data flow. Operations performed by functional units include: arithmetic operations, logical operations or conditional (i.e. comparison) operations. Note that the Miller application often uses the term xe2x80x9coperationxe2x80x9d to refer to what is herein called a functional unit. The logic synthesis link to behavioral synthesis is accomplished by Steps 1520 and 1530. Step 1520 performs a quick and approximate form of logic synthesis (i.e., technology mapping), in the midst of behavioral synthesis, to provide lower-level (typically gate-level or bit-level) circuit structure for the functional units that can then be timed by Step 1530. This lower-level representation is maintained in correspondence with the RTL description. Step 1530 performs pretiming of the circuit design produced by Step 1520, where timing information is added to the high-level functional units for use in subsequent behavioral synthesis operations. The subsequent behavioral synthesis operations are performed by Step 1540. The behavioral synthesis operations that can be performed include scheduling, resource sharing, allocation and post annotation. Once behavioral synthesis has been completed, and the circuit design has been fully optimized at a functional unit level, Step 1550 is executed such that a fully optimizing (and slow relative to Step 1520) form of logic synthesis can be done to result in an optimized gate-level description of the circuit design.
The scheduling operation of Step 1540 determines in which clock cycle each functional unit executes. The resource sharing operation of Step 1540 determines which functional units have hardware implementations that can be shared, for such reasons as their operating at mutually exclusive times. The allocation operation of Step 1540 maps the functional units into a specific hardware architecture, such as a xe2x80x9cdatapathxe2x80x9d comprising: memories, registers, arithmetic units, logical units and routing units. Functional units which require more than one clock cycle to execute are also annotated, by Step 1540, as requiring multiple cycles. This annotation prevents the logic optimizer 1550 from attempting to fit such functional units into a single cycle.
Scheduling is a crucial behavioral synthesis activity since its assignment of functional units to clocks cycles determines such key characteristics of the overall design implementation as: clock period, latency and throughput. The delay information, aquired by Step 1530, is essential to the scheduling process.
FIG. 2 depicts the basic procedure by which pretiming of a design, as called for by Step 1530 of FIG. 1, is accomplished in the Miller application. This procedure produces, for each functional unit, a xe2x80x9cchaining table.xe2x80x9d The chaining table provides the scheduling process of Step 1540 with delay information in a convenient form which allows the scheduler to readily ascertain the maximum number of functional units that can be fit into a clock cycle. Step 210 loops through each functional unit. For each functional unit iterated over, which shall be called the current functional unit, the following is performed. Step 220 sets all inputs of the current functional unit to time zero. All primary inputs of the circuit are set to minus infinity by Step 230. Note that inputs to the current functional unit which have been set to zero remain at zero regardless of whether it is fed by a primary input. Further note that between Steps 280 and 290 the inputs of the current functional unit must be released from their zero setting before the next current functional unit has its inputs set to zero by Step 220 in the next iteration. The entire circuit design is then timed using a conventional timing verifier (also known as a timing analyzer), such as Design Time or Prime Time, both available from Synopsys, Inc., 700 East Middlefield Road, Mountain View, Calif. Step 240. A chaining table data structure for the current functional unit, which we shall refer to as the current chaining table, is created. Step 245. Each chaining table data structure should be able to function as a set of tuples. Each tuple contains a functional unit identifier and a functional unit ready time for that functional unit, wherein the ready time has been determined relative to the current functional unit to which the chaining table is attached. In Step 250 the first entry to the current chaining table, such first entry having the ready time of the current functional unit, is added. Next, each functional unit in the transitive fanout of the current functional unit, which shall be referred to as the current fanout unit, is iterated over. Step 260. The ready time of each current fanout unit is recorded in the current chaining table. Step 270.
The procedure of FIG. 2 is limited to entering, in the current chaining table, those functional units which are part of the data flow (i.e. transitive fanout) of the current functional unit. For the purposes of scheduling, it is important to be able to augment the traversal of the RTL network (i.e., RTL description), by Step 260, to be beyond those functional units reachable solely by a data flow search. In particular, conditional functional units of the RTL network can be related to other functional units of the RTL network by xe2x80x9cactivation conditions.xe2x80x9d A definition of activation condition follows.
An xe2x80x9cactivation conditionxe2x80x9d is a signal line or lines of the RTL description which are caused to carry a control code in response to the evaluation of a comparator (or conditional) functional unit. In terms of the input Verilog HDL or VHDL description, an activation condition causes functionality, specified in a conditional statement, to be evaluated in response to the conditional expression portion of the conditional statement evaluating to a particular value. A typical exemplary conditional statement is of the form xe2x80x9cif ( less than conditional expression greater than ) then  less than activated functionality greater than  else  less than activated functionality greater than .xe2x80x9d For this example, items between angle brackets (xe2x80x9c less than xe2x80x9d or xe2x80x9c greater than xe2x80x9d) are meta-variables which are to be filled in with a programming language construct of the type described by the meta-variable. If  less than conditional expression greater than  evaluates to TRUE, then an activation condition is generated, in the corresponding RTL description, such as to cause the functionality specified by  less than activated functionality1 greater than  to be performed. Similarly, if  less than conditional expression greater than  evaluates to FALSE, then another activation condition is generated, in the corresponding RTL description, such as to cause the functionality specified by  less than activated functionality2 greater than  to be performed. The final output, of that portion of the RTL description that models the  less than conditional expression greater than , is from a comparator functional unit. It is this comparator functional unit that drives, typically through a buffer and an inverter, the activation conditions. The buffer or inverter for driving an activation condition is not a type of functional unit.
It is often the case that a conditional statement is translated into an RTL description where the activation condition: i) is wired to select an input of one or more multiplexors and ii) indicates the RTL functional units (which we shall refer is to collectively as the activation condition""s xe2x80x9cactivated cellsxe2x80x9d) that are to be evaluated. In such cases, each multiplexor is preferably controlled by xe2x80x9c1-hotxe2x80x9d encoding, as such encoding is commonly known in the art of digital hardware design. The number of multiplexors is determined by the number variables that are assigned a new value as a result of the conditional statement. It is also typically the case that the activated cells are within the transitive fanin of the selected multiplexor inputs. An example of a Verilog HDL program, and the activation conditions it produces, are shown in FIGS. 6A and 6B. FIG. 6A depicts the Verilog HDL source code, while FIG. 6B depicts a circuit representation determined from it. FIG. 6B depicts four activation conditions numbered: 635, 640, 645 and 650. Activation conditions 645 and 650 are the result of evaluating conditional functional unit 630, while activation conditions 635 and 640 are the result of evaluating conditional functional unit 625. Activation condition 650 corresponds to the xe2x80x9celsexe2x80x9d clause, if the test for x less than y is FALSE. Note that the activation condition 650 only indicates its activated cells to be comparator 625, since that is the only functional unit which is necessarily executed. Activation condition 645 indicates its activated cells are adder functional unit 615 and subtractor functional unit 610. Activation condition 635 indicates its activated cells to be adder functional unit 620, while activation condition 640 has no functional units executed in response to its assertion.
Alternatively, an activation condition may simply indicate activated cells, without also controlling a multiplexor. An example of such a multiplexor-less activation condition would be, for example, an activation condition which activates a functional unit that writes data to a memory address upon being activated. Such an activation condition could result from a Verilog HDL or VHDL description regarding the writing of data into an array, where the data written into the array depends upon the evaluation of a conditional statement. Step 1510 would typically translate such an array into an RTL-level block of random-access memory (RAM). A functional unit would typically be created to represent the action of storing one type of data, into the selected address of the RAM, if the conditional expression of the conditional statement evaluates to a particular value. In response to the conditional expression evaluating to other values, other functional units, storing other types of data into the RAM, could be activated. An example of such a Verilog HDL program, and the activation conditions it produces, are shown in FIGS. 7A and 7B. FIG. 7A shows that if the conditional expression x less than y is TRUE, then a+b is stored in the RAM xe2x80x9cmemxe2x80x9d at address xe2x80x9caddr,xe2x80x9d whereas otherwise the value of b is stored in xe2x80x9cmemxe2x80x9d at address xe2x80x9caddr.xe2x80x9d In FIG. 7B, conditional expression xe2x80x9cx less than yxe2x80x9d becomes conditional functional unit 700 which produces activation conditions 710 (if functional unit 700 produces a TRUE) and 705 (if functional unit 700 produces a FALSE). As can be seen, activation conditions 710 and 705 only indicate functional units as activated cells to be evaluated and are not wired to select a multiplexor input. Specifically, activation condition 710 indicates that its activated cells are adder 725 and memory write operation 720, while activation condition 705 indicates that its activated cell is memory write operation 715.
It should be noted that the activated cells, for an activation condition, are merely indicated (by, for example, a list associated with the activation condition) and are not wired to the activation condition such that they are in the activation condition""s transitive fanout.
Since Step 260 of the pretiming procedure of FIG. 2 only follows the transitive fanout of the current functional unit, it is not able to traverse activation conditions and include the additional functional units, that would be located by such an augmented network traversal, in the chaining table of the current functional unit.
It is useful, for scheduling purposes, to traverse activation conditions, during chaining table creation, by considering the functional unit directly driving an activation condition as occurring temporaly before those functional units indicated as the activated cells of the activation condition.
Since activation conditions indicate a flow of control, as opposed to data flow, traversal of activation conditions for purposes of creating chaining table entries is referred to as xe2x80x9ccontrol chaining.xe2x80x9d
Control chaining is useful because it permits advanced scheduling techniques in which the computation of a conditional functional unit can be considered for scheduling in the same clock cycle as the functional units that depend on the evaluation of that conditional functional unit.
The desired default temporal relation, for most practical purposes, is a scheduling of the conditional functional unit in serial with those functional units that depend on it. This type of serialization tends to save area in the resulting integrated circuit design by providing greater opportunity for hardware to be shared among the functional units. For example, since the result of the conditional functional unit is already known when the functional units that depend on it need to calculate their values, the same piece of hardware may be used for both: i) the functional units activated for a TRUE result of the conditional functional unit and ii) the functional units activated for a FALSE result of the same conditional functional unit.
The Miller application addresses the problem of control chaining by adding special procedures to the basic pretiming procedure of FIG. 2.
The control chaining procedures of the Miller application are relatively complex and slow. These procedures are particularly slow when pretiming of xe2x80x9cnestedxe2x80x9d activation conditions is to be accomplished. An example of nested activation conditions is shown in FIG. 6B where activation conditions 635 and 640 are xe2x80x9cnestedxe2x80x9d within activation condition 650. This is due to the fact that the conditional statement testing for u less than v is nested within the conditional statement testing for x less than y. In general, a nesting of conditional statements results in a nesting of activation conditions.
It would be desirable to increase the overall speed of behavioral synthesis by eliminating the additional processing, of the pretiming process 1530, associated with control chaining as described in the Miller application.
The present invention permits behavioral synthesis to be accomplished with control chaining information, but with the control chaining information determined by a basic data-flow based pretiming. Thus the present invention speeds up the step of pretiming, with respect to the Miller application, by eliminating its additional processing for determining control chaining ready times. Additional control chaining procedures are eliminated by adding the following two steps to the behavioral synthesis process: i) following the translation of the HLHDL into an RTL circuit description, but before the step of pretiming, the RTL description is temporarily altered such that the functional units activated by each control signal (i.e. activation condition) are in the transitive fanout of their control signal; and ii) once pretiming has been accomplished, the circuit representation is reverted back to its original state. Other than these two additional steps, the known process for behavioral synthesis can be followed.
The RTL circuit description is temporarily altered by the following triply-nested loops. Each activation condition is looped over (yielding a current activation condition for each iteration), and within this loop each activated cell of the current activation condition is looped over (yielding a current activated cell for each iteration). The current activated cell is put within the transitive fanout of the current activation condition by looping over each input of the current activated cell (yielding a current activated cell input for each iteration) and performing the following alteration upon it. A xe2x80x9cchaining cell,xe2x80x9d referred to as the current chaining cell, is inserted between the current activated cell input and the source driving the current activated cell input (this source for driving the current activated cell input being referred to as the xe2x80x9cdriving outputxe2x80x9d). A chaining cell consists of a two-input AND gate (of zero delay) for each bit of the current activated cell input. Each bit of the current activated cell input is driven by the output of a different two-input AND gate of the current chaining cell. One input of each AND gate is connected to the corresponding bit of the driving output. The other input of each AND gate of the current chaining cell is connected to the current activation condition.
Due to chaining cells increasing the loading of activation condition nodes, it may also be desirable to annotate activation condition nodes with directives instructing the timing analyzer, utilized in pretiming, to count the activation condition nodes as having zero propagation delay.
Reverting the RTL circuit description, after the pretiming has been accomplished, is performed by a procedure which is very similar to the above triply-nested loops for altering the RTL circuit description, except that within the innermost loop, the current chaining cell is removed from the current activated cell input and the current chaining cell is disconnected from the current activation condition. Reversion does not remove the chaining tables produced by pretiming and therefore these tables are available for the subsequent steps of behavioral synthesis.
Advantages of the invention will be set forth, in part, in the description that follows and, in part, will be understood by those skilled in the art from the description or may be learned by practice of the invention. The advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims and equivalents.